// 动态规划 时间 O(n) 空间 O(1)
/*
class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (n == 2) return 1;
        int i = 0, j = 1, k = 1;
        int ret;
        for (int s = 3; s <= n; s++) {
            ret = i + j + k;
            i = j;
            j = k;
            k = ret;
        }
        return ret;
    }
};
*/

// 打表 时间 O(1) 空间 O(array size)
/*
class Solution {
public:
    int tribonacci(int n) {
        int ret[38] = {0, 1, 1, 2, 4, 7, 13, 24, 44, 81,
                       149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890,
                       66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591,
                       29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852, 2082876103};
        return ret[n];
    }
};
*/

// 矩阵快速幂 时间 O(log n) 空间 O(1)
